//编译环境 vs2019

/*
* 【快速排序】：每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，
*              将大于等于基准点的数全部放到基准点的右边
*/
#include<stdio.h>
#pragma warning(disable:4996);

#define SIZE 10

void quick_sort(int num[], int left, int right)
{
    int i, j, temp;
    int tmp;

    i = left;
    j = right;
    tmp = num[left];  //通常第一个元素是基准数

    if (i > j)  //如果下标i大于下标j，函数结束运行
    {
        return;
    }

    while (i != j) //i和j未相遇
    {
        //顺序很重要，要先从右往左找
        //j一步步往左挪，直到找到比【tmp】基准数小的停下来
        while (num[j] >= tmp && j > i)
        {
            j--;
        }
        //再从左往右找
        //i一步步往右挪，直到找到比【tmp】基准数大的停下来
        while (num[i] <= tmp && j > i)
        {
            i++;
        }
        //i和j未相遇时交换两个数在数组中的位置
        if (j > i)
        {
            temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }
    //i与j相遇，最终将基准数归位
    num[left] = num[i];
    num[i] = tmp;

    quick_sort(num, left, i - 1);//继续处理上轮基准数左边的数据，这里是一个递归的过程
    quick_sort(num, i + 1, right);//继续处理上轮基准数右边的数据，这里是一个递归的过程

    return;
}

int main(int argc, char** argv)
{
    //创建一个数组
    int num[SIZE] = { 0 };
    int i;

    //输入数字
    for (i = 0; i < SIZE; i++)
    {
        scanf("%d", &num[i]);
    }
    //调用快速排序
    quick_sort(num, 0, SIZE - 1);
    //输出排序后的结果
    for (i = 0; i < SIZE; i++)
    {
        printf(" %d ", num[i]);
    }

    return 0;
}
